﻿using System;
using System.Buffers;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.IO;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace IndexedFilePackageLibrary
{
    public class IndexedFilePackage : IDisposable
    {
        private const int _FileHeaderSize = 16;

        private static readonly ArrayPool<byte> s_arrayPool = ArrayPool<byte>.Shared;
        private static readonly UTF8Encoding s_encoding = new UTF8Encoding(encoderShouldEmitUTF8Identifier: false);

        private readonly string _path;
        private FileStream _stream;
        private readonly short _maxItemsCountPerNode;
        private readonly int _headersLength;
        private readonly int _flags;

        private readonly bool _useIntFileSize;

        private IndexedFilePackage(string path, FileStream stream, short maxItemsCountPerNode, int headersLength, int flags)
        {
            _path = path;
            _stream = stream;
            _maxItemsCountPerNode = maxItemsCountPerNode;
            _headersLength = headersLength;
            _flags = flags;

            _useIntFileSize = 0 != (flags & 0b1);
        }

        private static FileStream OpenReadStream(string path, bool useAsync = true)
        {
            return new FileStream(path, FileMode.Open, FileAccess.Read, FileShare.Read, 4096, useAsync);
        }
        private static FileStream OpenWriteStream(string path, bool useAsync = true)
        {
            return new FileStream(path, FileMode.CreateNew, FileAccess.Write, FileShare.None, 4096, useAsync);
        }

        public static IndexedFilePackage Open(string path, bool useAsyncStream = false)
        {
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }

            // 打开文件
            var stream = OpenReadStream(path, useAsyncStream);
            try
            {
                long length = stream.Length;
                if (length < _FileHeaderSize)
                {
                    throw new InvalidDataException("File length too short.");
                }

                // 读取MAGIC
                // OPTIMIZATION 使用stackalloc
                var bBuffer = s_arrayPool.Rent(_FileHeaderSize);
                int flags;
                short maxItemsCountPerNode;
                int headers_length;
                try
                {
                    stream.Read(bBuffer, 0, _FileHeaderSize);

                    if (bBuffer[0] != 'I' || bBuffer[1] != 'F' || bBuffer[2] != 'P' || bBuffer[3] != '1')
                    {
                        throw new InvalidDataException("Wrong magic number.");
                    }

                    flags = Unsafe.As<byte, int>(ref bBuffer[4]);
                    maxItemsCountPerNode = Unsafe.As<byte, short>(ref bBuffer[10]);

                    //读取indexes-length
                    headers_length = Unsafe.As<byte, int>(ref bBuffer[12]);
                    if (headers_length < 0)
                    {
                        throw new InvalidDataException("headers-length is negative.");
                    }
                }
                finally
                {
                    s_arrayPool.Return(bBuffer);
                }

                var ifp = new IndexedFilePackage(path, stream, maxItemsCountPerNode, headers_length, flags);
                stream = null;
                return ifp;
            }
            finally
            {
                if (stream != null)
                {
                    stream.Dispose();
                }
            }

        }
        public static async Task<IndexedFilePackage> OpenAsync(string path)
        {
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }

            // 打开文件
            var stream = OpenReadStream(path, true);
            try
            {
                long length = stream.Length;
                if (length < _FileHeaderSize)
                {
                    throw new InvalidDataException("File length too short.");
                }

                // 读取MAGIC
                // OPTIMIZATION 使用stackalloc
                var bBuffer = s_arrayPool.Rent(_FileHeaderSize);
                int flags;
                short maxItemsCountPerNode;
                int headers_length;
                try
                {
                    await stream.ReadAsync(bBuffer, 0, _FileHeaderSize).ConfigureAwait(false);

                    if (bBuffer[0] != 'I' || bBuffer[1] != 'F' || bBuffer[2] != 'P' || bBuffer[3] != '1')
                    {
                        throw new InvalidDataException("Wrong magic number.");
                    }

                    flags = Unsafe.As<byte, int>(ref bBuffer[4]);
                    maxItemsCountPerNode = Unsafe.As<byte, short>(ref bBuffer[10]);

                    //读取indexes-length
                    headers_length = Unsafe.As<byte, int>(ref bBuffer[12]);
                    if (headers_length < 0)
                    {
                        throw new InvalidDataException("headers-length is negative.");
                    }
                }
                finally
                {
                    s_arrayPool.Return(bBuffer);
                }

                var ifp = new IndexedFilePackage(path, stream, maxItemsCountPerNode, headers_length, flags);
                stream = null;
                return ifp;
            }
            finally
            {
                if (stream != null)
                {
                    stream.Dispose();
                }
            }

        }

        public IndexedFilePackage OpenNew(bool? useAsync = null)
        {
            EnsureNotDisposed();

            return new IndexedFilePackage(_path, OpenReadStream(_path, useAsync == null ? _stream.IsAsync : useAsync.Value), _maxItemsCountPerNode, _headersLength, _flags);
        }

        public FileIndexNode FindFile(string fileName)
        {
            if (fileName == null)
            {
                throw new ArgumentNullException(nameof(fileName));
            }
            if (fileName == "")
            {
                throw new ArgumentException("File name can not be empty.", nameof(fileName));
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            var fileNameEncoded = new ReadOnlySpan<byte>(s_encoding.GetBytes(fileName));
            uint fileNameHash = StringHash.Fnv1a.Hash32(fileNameEncoded);

            int maxIndexNodeFixedLength = 18 * _maxItemsCountPerNode + 12;
            byte[] nodeDataBuffer = s_arrayPool.Rent(maxIndexNodeFixedLength);
            try
            {
                int headerSkipCount = _FileHeaderSize + _headersLength;
                // 根节点
                int offset = 0;

                while (true)
                {
                    // 读取节点信息进内存
                    _stream.Seek(headerSkipCount + offset, SeekOrigin.Begin);
                    _stream.Read(nodeDataBuffer, 0, maxIndexNodeFixedLength);

                    // 读取有效节点个数
                    short itemsCount = Unsafe.As<byte, short>(ref nodeDataBuffer[0]);
                    if (itemsCount == 0)
                    {
                        // 0个元素的节点
                        return null;
                    }
                    if (itemsCount < _maxItemsCountPerNode)
                    {
                        _stream.Seek(headerSkipCount + offset + 18 * itemsCount + 12, SeekOrigin.Begin);
                    }


                    var fileIndexPointerList = MemoryMarshal.Cast<byte, int>(new ReadOnlySpan<byte>(nodeDataBuffer, 4, 4 * (itemsCount + 1)));
                    var fileHashList = MemoryMarshal.Cast<byte, uint>(new ReadOnlySpan<byte>(nodeDataBuffer, 8 + 4 * itemsCount, 4 * itemsCount));
                    var fileOffsetList = MemoryMarshal.Cast<byte, long>(new ReadOnlySpan<byte>(nodeDataBuffer, 8 + 8 * itemsCount, 8 * itemsCount));
                    var fileNameSizeList = MemoryMarshal.Cast<byte, ushort>(new ReadOnlySpan<byte>(nodeDataBuffer, 8 + 16 * itemsCount, 2 * itemsCount));

                    // 用二分查找找到最近的节点
                    InternalBinarySearchResult searchResult;
                    searchResult = InternalBinarySearch(fileHashList, itemsCount, fileNameHash);

                    // 是否转到下一层
                    if (searchResult.CompareResult < 0) // fileNameHash < current
                    {
                        int newOffset = fileIndexPointerList[searchResult.Index];
                        if (newOffset == 0)
                        {
                            return null;
                        }
                        if (newOffset < 0)
                        {
                            throw new InvalidDataException();
                        }
                        offset = newOffset;
                        continue;
                    }
                    else if (searchResult.CompareResult > 0) // fileNameHash > current
                    {
                        int newOffset = fileIndexPointerList[searchResult.Index + 1];
                        if (newOffset == 0)
                        {
                            return null;
                        }
                        if (newOffset < 0)
                        {
                            throw new InvalidDataException();
                        }
                        offset = newOffset;
                        continue;
                    }

                    // 扩展搜索范围
                    int searchStart = searchResult.Index;
                    while (searchStart > 0 && fileHashList[searchStart - 1] == fileNameHash) searchStart--;
                    int searchEnd = searchResult.Index;
                    while (searchEnd < fileHashList.Length - 1 && fileHashList[searchEnd + 1] == fileNameHash) searchEnd++;

                    // 读取文件名域
                    int searchLength = searchEnd - searchStart + 1;
                    byte[] fileNameIndexesBuffer = s_arrayPool.Rent(4 * searchLength);
                    Span<int> fileNameIndexes = MemoryMarshal.Cast<byte, int>(new Span<byte>(fileNameIndexesBuffer, 0, 4 * searchLength));

                    int fileNameSkippedSize = 0;
                    int fileNameTotalLength = 0;
                    for (int i = 0; i < searchStart; i++)
                        fileNameSkippedSize += fileNameSizeList[i];
                    for (int i = searchStart, j = 0; i <= searchEnd; i++, j++)
                    {
                        fileNameIndexes[j] = fileNameTotalLength;
                        fileNameTotalLength += fileNameSizeList[i];
                    }
                    fileNameSizeList = fileNameSizeList.Slice(searchStart, searchLength);
                    byte[] targetFileNameList = s_arrayPool.Rent(fileNameTotalLength);
                    try
                    {
                        // 读取范围内文件名数据
                        _stream.Seek(fileNameSkippedSize, SeekOrigin.Current);
                        _stream.Read(targetFileNameList, 0, fileNameTotalLength);

                        // 对文件名使用二分查找法
                        searchResult = InternalBinarySearchForFileName(new ReadOnlySpan<byte>(targetFileNameList, 0, fileNameTotalLength), fileNameIndexes, fileNameSizeList, fileNameEncoded);
                        // 是否转到下一层
                        if (searchResult.CompareResult < 0) // fileName < current
                        {
                            int newOffset = fileIndexPointerList[searchStart + searchResult.Index];
                            if (newOffset == 0)
                            {
                                return null;
                            }
                            if (newOffset < 0)
                            {
                                throw new InvalidDataException();
                            }
                            offset = newOffset;
                            continue;
                        }
                        else if (searchResult.CompareResult > 0) // fileName > current
                        {
                            int newOffset = fileIndexPointerList[searchStart + searchResult.Index + 1];
                            if (newOffset == 0)
                            {
                                return null;
                            }
                            if (newOffset < 0)
                            {
                                throw new InvalidDataException();
                            }
                            offset = newOffset;
                            continue;
                        }

                        // 找到元素
                        return new FileIndexNode(this)
                        {
                            FileName = fileName,
                            FileOffset = fileOffsetList[searchStart + searchResult.Index]
                        };
                    }
                    finally
                    {
                        s_arrayPool.Return(fileNameIndexesBuffer);
                        s_arrayPool.Return(targetFileNameList);
                    }
                }
            }
            finally
            {
                s_arrayPool.Return(nodeDataBuffer);
            }
        }
        public async Task<FileIndexNode> FindFileAsync(string fileName)
        {
            if (fileName == null)
            {
                throw new ArgumentNullException(nameof(fileName));
            }
            if (fileName == "")
            {
                throw new ArgumentException("File name can not be empty.", nameof(fileName));
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            var fileNameEncoded = s_encoding.GetBytes(fileName);
            uint fileNameHash = StringHash.Fnv1a.Hash32((ReadOnlySpan<byte>)fileNameEncoded);

            int maxIndexNodeFixedLength = 18 * _maxItemsCountPerNode + 12;
            byte[] nodeDataBuffer = s_arrayPool.Rent(maxIndexNodeFixedLength);
            try
            {
                int headerSkipCount = _FileHeaderSize + _headersLength;
                // 根节点
                int offset = 0;

                while (true)
                {
                    // 读取节点信息进内存
                    _stream.Seek(headerSkipCount + offset, SeekOrigin.Begin);
                    await _stream.ReadAsync(nodeDataBuffer, 0, maxIndexNodeFixedLength).ConfigureAwait(false);

                    // 读取有效节点个数
                    short itemsCount = Unsafe.As<byte, short>(ref nodeDataBuffer[0]);
                    if (itemsCount == 0)
                    {
                        // 0个元素的节点
                        return null;
                    }
                    if (itemsCount < _maxItemsCountPerNode)
                    {
                        _stream.Seek(headerSkipCount + offset + 18 * itemsCount + 12, SeekOrigin.Begin);
                    }
                    var fileIndexPointerList = new ReadOnlyMemory<byte>(nodeDataBuffer, 4, 4 * (itemsCount + 1));
                    var fileHashList = new ReadOnlyMemory<byte>(nodeDataBuffer, 8 + 4 * itemsCount, 4 * itemsCount);
                    var fileOffsetList = new ReadOnlyMemory<byte>(nodeDataBuffer, 8 + 8 * itemsCount, 8 * itemsCount);
                    var fileNameSizeList = new ReadOnlyMemory<byte>(nodeDataBuffer, 8 + 16 * itemsCount, 2 * itemsCount);

                    // 用二分查找找到最近的节点
                    InternalBinarySearchResult searchResult;
                    searchResult = InternalBinarySearch(MemoryMarshal.Cast<byte, uint>(fileHashList.Span), itemsCount, fileNameHash);

                    // 是否转到下一层
                    if (searchResult.CompareResult < 0) // fileNameHash < current
                    {
                        int newOffset = MemoryMarshal.Cast<byte, int>(fileIndexPointerList.Span)[searchResult.Index];
                        if (newOffset == 0)
                        {
                            return null;
                        }
                        if (newOffset < 0)
                        {
                            throw new InvalidDataException();
                        }
                        offset = newOffset;
                        continue;
                    }
                    else if (searchResult.CompareResult > 0) // fileNameHash > current
                    {
                        int newOffset = MemoryMarshal.Cast<byte, int>(fileIndexPointerList.Span)[searchResult.Index + 1];
                        if (newOffset == 0)
                        {
                            return null;
                        }
                        if (newOffset < 0)
                        {
                            throw new InvalidDataException();
                        }
                        offset = newOffset;
                        continue;
                    }

                    // 扩展搜索范围
                    int searchStart = searchResult.Index;
                    int searchEnd = 0;
                    ExpandSearch(MemoryMarshal.Cast<byte, uint>(fileHashList.Span), ref searchStart, ref searchEnd);

                    void ExpandSearch(ReadOnlySpan<uint> _fileHashList, ref int _searchStart, ref int _searchEnd)
                    {
                        int start = _searchStart;
                        _searchStart = start;
                        while (_searchStart > 0 && _fileHashList[_searchStart - 1] == fileNameHash) _searchStart--;
                        _searchEnd = start;
                        while (_searchEnd < _fileHashList.Length - 1 && _fileHashList[_searchEnd + 1] == fileNameHash) _searchEnd++;
                    }

                    // 读取文件名域
                    int searchLength = searchEnd - searchStart + 1;
                    byte[] fileNameIndexesBuffer = s_arrayPool.Rent(4 * searchLength);
                    var fileNameIndexes = new Memory<byte>(fileNameIndexesBuffer, 0, 4 * searchLength);

                    int fileNameSkippedSize = 0;
                    int fileNameTotalLength = 0;
                    for (int i = 0; i < searchStart; i++)
                        fileNameSkippedSize += MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i];
                    for (int i = searchStart, j = 0; i <= searchEnd; i++, j++)
                    {
                        MemoryMarshal.Cast<byte, int>(fileNameIndexes.Span)[j] = fileNameTotalLength;
                        fileNameTotalLength += MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i];
                    }
                    byte[] targetFileNameList = s_arrayPool.Rent(fileNameTotalLength);
                    try
                    {
                        // 读取范围内文件名数据
                        _stream.Seek(fileNameSkippedSize, SeekOrigin.Current);
                        await _stream.ReadAsync(targetFileNameList, 0, fileNameTotalLength).ConfigureAwait(false);

                        // 对文件名使用二分查找法
                        searchResult = InternalBinarySearchForFileName(new ReadOnlySpan<byte>(targetFileNameList, 0, fileNameTotalLength), MemoryMarshal.Cast<byte, int>(fileNameIndexes.Span), MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span).Slice(searchStart, searchLength), (ReadOnlySpan<byte>)fileNameEncoded);
                        // 是否转到下一层
                        if (searchResult.CompareResult < 0) // fileName < current
                        {
                            int newOffset = MemoryMarshal.Cast<byte, int>(fileIndexPointerList.Span)[searchStart + searchResult.Index];
                            if (newOffset == 0)
                            {
                                return null;
                            }
                            if (newOffset < 0)
                            {
                                throw new InvalidDataException();
                            }
                            offset = newOffset;
                            continue;
                        }
                        else if (searchResult.CompareResult > 0) // fileName > current
                        {
                            int newOffset = MemoryMarshal.Cast<byte, int>(fileIndexPointerList.Span)[searchStart + searchResult.Index + 1];
                            if (newOffset == 0)
                            {
                                return null;
                            }
                            if (newOffset < 0)
                            {
                                throw new InvalidDataException();
                            }
                            offset = newOffset;
                            continue;
                        }

                        // 找到元素
                        return new FileIndexNode(this)
                        {
                            FileName = fileName,
                            FileOffset = MemoryMarshal.Cast<byte, long>(fileOffsetList.Span)[searchStart + searchResult.Index]
                        };
                    }
                    finally
                    {
                        s_arrayPool.Return(fileNameIndexesBuffer);
                        s_arrayPool.Return(targetFileNameList);
                    }
                }
            }
            finally
            {
                s_arrayPool.Return(nodeDataBuffer);
            }
        }

        private InternalBinarySearchResult InternalBinarySearch(ReadOnlySpan<uint> data, int itemsCount, uint targetElement)
        {
            int start = 0;
            int end = itemsCount - 1;
            uint element;
            while (true)
            {
                if (start == end)
                {
                    // 1个元素
                    return new InternalBinarySearchResult(start, targetElement.CompareTo(data[start]));
                }
                if (start == end - 1)
                {
                    // 2个元素
                    element = data[start];
                    if (targetElement < element)
                        return new InternalBinarySearchResult(start, -1);
                    if (targetElement == element)
                        return new InternalBinarySearchResult(start, 0);
                    return new InternalBinarySearchResult(end, targetElement.CompareTo(data[end]));
                }
                int mid = (start + end) / 2;
                element = data[mid];
                if (targetElement < element)
                    end = mid - 1;
                else if (targetElement > element)
                    start = mid + 1;
                else
                    return new InternalBinarySearchResult(mid, 0);
            }
        }
        private struct InternalBinarySearchResult
        {
            public int Index { get; private set; }
            public int CompareResult { get; private set; } // target - current
            public InternalBinarySearchResult(int index, int compareResult)
            {
                Index = index;
                CompareResult = compareResult;
            }
        }
        private InternalBinarySearchResult InternalBinarySearchForFileName(ReadOnlySpan<byte> buffer, ReadOnlySpan<int> indexesPointer, ReadOnlySpan<ushort> fileNameSizeList, ReadOnlySpan<byte> targetElement)
        {
            Debug.Assert(indexesPointer.Length == fileNameSizeList.Length);

            int start = 0;
            int end = indexesPointer.Length - 1;
            ReadOnlySpan<byte> element;
            while (true)
            {
                if (start == end)
                {
                    // 1个元素
                    return new InternalBinarySearchResult(start, FileNameHelper.CompareFileNameNoHash(targetElement, buffer.Slice(indexesPointer[start], fileNameSizeList[start])));
                }
                if (start == end - 1)
                {
                    // 2个元素
                    element = buffer.Slice(indexesPointer[start], fileNameSizeList[start]);
                    int compare = FileNameHelper.CompareFileNameNoHash(targetElement, element);
                    if (compare < 0)
                        return new InternalBinarySearchResult(start, -1);
                    if (compare == 0)
                        return new InternalBinarySearchResult(start, 0);
                    return new InternalBinarySearchResult(end, FileNameHelper.CompareFileNameNoHash(targetElement, buffer.Slice(indexesPointer[end], fileNameSizeList[end])));
                }
                int mid = (start + end) / 2;
                element = buffer.Slice(indexesPointer[mid], fileNameSizeList[mid]);
                switch (FileNameHelper.CompareFileNameNoHash(targetElement, element))
                {
                    case 1: // targetElement > element
                        start = mid + 1;
                        break;
                    case -1: // targetElement < element
                        end = mid - 1;
                        break;
                    default: // targetElement = element
                        return new InternalBinarySearchResult(mid, FileNameHelper.CompareFileNameNoHash(targetElement, element));
                }
            }
        }

        public FileIndexNode[] FindAllNodes()
        {
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            var list = new List<FileIndexNode>();
            int maxIndexNodeFixedLength = 18 * _maxItemsCountPerNode + 12;
            byte[] nodeDataBuffer = s_arrayPool.Rent(maxIndexNodeFixedLength);
            try
            {
                int headerSkipCount = _FileHeaderSize + _headersLength;
                // 从根节点开始
                int offset = 0;

                do
                {
                    // 读取节点信息进内存
                    _stream.Seek(headerSkipCount + offset, SeekOrigin.Begin);
                    _stream.Read(nodeDataBuffer, 0, maxIndexNodeFixedLength);

                    // 读取有效节点个数
                    short itemsCount = Unsafe.As<byte, short>(ref nodeDataBuffer[0]);
                    // 读取下一个节点位置
                    offset = Unsafe.As<byte, int>(ref nodeDataBuffer[18 * itemsCount + 8]);
                    if (itemsCount == 0)
                    {
                        continue;
                    }
                    int remainingBytes = 18 * (_maxItemsCountPerNode - itemsCount);

                    // 准备各字段
                    var fileOffsetList = MemoryMarshal.Cast<byte, long>(new ReadOnlySpan<byte>(nodeDataBuffer, 8 + 8 * itemsCount, 8 * itemsCount));
                    var fileNameSizeList = MemoryMarshal.Cast<byte, ushort>(new ReadOnlySpan<byte>(nodeDataBuffer, 8 + 16 * itemsCount, 2 * itemsCount));

                    // 准备读取文件名域
                    int fileNameTotalLength = 0;
                    int overflowIndex = itemsCount;
                    int alreadyReadCount = 0;
                    for (int i = 0; i < itemsCount; i++)
                    {
                        fileNameTotalLength += fileNameSizeList[i];
                        remainingBytes -= fileNameSizeList[i];
                        if (overflowIndex > i && remainingBytes < 0)
                        {
                            overflowIndex = i;
                            alreadyReadCount = fileNameSizeList[i] + remainingBytes;
                        }
                    }
                    remainingBytes = -remainingBytes;

                    byte[] fileNameBuffer = s_arrayPool.Rent(fileNameTotalLength);
                    try
                    {
                        // 读取文件名域
                        if (overflowIndex < itemsCount)
                        {
                            Buffer.BlockCopy(nodeDataBuffer, maxIndexNodeFixedLength - alreadyReadCount, fileNameBuffer, 0, alreadyReadCount);
                        }
                        if (remainingBytes > 0)
                        {
                            _stream.Read(fileNameBuffer, alreadyReadCount, remainingBytes);
                        }

                        // 获得每一个索引
                        int originalBufferReadCount = 18 * itemsCount + 12;
                        int overflowBufferReadCount = 0;
                        for (int i = 0; i < itemsCount; i++)
                        {
                            string fileName;
                            if (i >= overflowIndex)
                            {
                                fileName = s_encoding.GetString(fileNameBuffer, overflowBufferReadCount, fileNameSizeList[i]);
                                overflowBufferReadCount += fileNameSizeList[i];
                            }
                            else
                            {
                                fileName = s_encoding.GetString(nodeDataBuffer, originalBufferReadCount, fileNameSizeList[i]);
                                originalBufferReadCount += fileNameSizeList[i];
                            }
                            list.Add(new FileIndexNode(this)
                            {
                                FileName = fileName,
                                FileOffset = fileOffsetList[i]
                            });
                        }
                    }
                    finally
                    {
                        s_arrayPool.Return(fileNameBuffer);
                    }

                } while (offset != 0);
            }
            finally
            {
                s_arrayPool.Return(nodeDataBuffer);
            }

            return list.ToArray();
        }
        public async Task<FileIndexNode[]> FindAllNodesAsync()
        {
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            var list = new List<FileIndexNode>();
            int maxIndexNodeFixedLength = 18 * _maxItemsCountPerNode + 12;
            byte[] nodeDataBuffer = s_arrayPool.Rent(maxIndexNodeFixedLength);
            try
            {
                int headerSkipCount = _FileHeaderSize + _headersLength;
                // 从根节点开始
                int offset = 0;

                do
                {
                    // 读取节点信息进内存
                    _stream.Seek(headerSkipCount + offset, SeekOrigin.Begin);
                    await _stream.ReadAsync(nodeDataBuffer, 0, maxIndexNodeFixedLength).ConfigureAwait(false);

                    // 读取有效节点个数
                    short itemsCount = Unsafe.As<byte, short>(ref nodeDataBuffer[0]);
                    // 读取下一个节点位置
                    offset = Unsafe.As<byte, int>(ref nodeDataBuffer[18 * itemsCount + 8]);
                    if (itemsCount == 0)
                    {
                        continue;
                    }
                    int remainingBytes = 18 * (_maxItemsCountPerNode - itemsCount);

                    // 准备各字段
                    ReadOnlyMemory<byte> fileOffsetList = new ReadOnlyMemory<byte>(nodeDataBuffer, 8 + 8 * itemsCount, 8 * itemsCount);
                    ReadOnlyMemory<byte> fileNameSizeList = new ReadOnlyMemory<byte>(nodeDataBuffer, 8 + 16 * itemsCount, 2 * itemsCount);

                    // 准备读取文件名域
                    int fileNameTotalLength = 0;
                    int overflowIndex = itemsCount;
                    int alreadyReadCount = 0;
                    for (int i = 0; i < itemsCount; i++)
                    {
                        fileNameTotalLength += MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i];
                        remainingBytes -= MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i];
                        if (overflowIndex > i && remainingBytes < 0)
                        {
                            overflowIndex = i;
                            alreadyReadCount = MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i] + remainingBytes;
                        }
                    }
                    remainingBytes = -remainingBytes;

                    byte[] fileNameBuffer = s_arrayPool.Rent(fileNameTotalLength);
                    try
                    {
                        // 读取文件名域
                        if (overflowIndex < itemsCount)
                        {
                            Buffer.BlockCopy(nodeDataBuffer, maxIndexNodeFixedLength - alreadyReadCount, fileNameBuffer, 0, alreadyReadCount);
                        }
                        if (remainingBytes > 0)
                        {
                            await _stream.ReadAsync(fileNameBuffer, alreadyReadCount, remainingBytes).ConfigureAwait(false);
                        }

                        // 获得每一个索引
                        int originalBufferReadCount = 18 * itemsCount + 12;
                        int overflowBufferReadCount = 0;
                        for (int i = 0; i < itemsCount; i++)
                        {
                            string fileName;
                            if (i >= overflowIndex)
                            {
                                fileName = s_encoding.GetString(fileNameBuffer, overflowBufferReadCount, MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i]);
                                overflowBufferReadCount += MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i];
                            }
                            else
                            {
                                fileName = s_encoding.GetString(nodeDataBuffer, originalBufferReadCount, MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i]);
                                originalBufferReadCount += MemoryMarshal.Cast<byte, ushort>(fileNameSizeList.Span)[i];
                            }
                            list.Add(new FileIndexNode(this)
                            {
                                FileName = fileName,
                                FileOffset = MemoryMarshal.Cast<byte, long>(fileOffsetList.Span)[i]
                            });
                        }
                    }
                    finally
                    {
                        s_arrayPool.Return(fileNameBuffer);
                    }

                } while (offset != 0);
            }
            finally
            {
                s_arrayPool.Return(nodeDataBuffer);
            }

            return list.ToArray();
        }


        public FileInfo GetFileInfo(FileIndexNode file)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (!file.SkipParentValidation && !ReferenceEquals(file.Parent, this))
            {
                throw new InvalidOperationException("Parent object mismatch!");
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            _stream.Seek(file.FileOffset, SeekOrigin.Begin);

            byte[] buffer = s_arrayPool.Rent(256);
            try
            {

                // 读取节点头部
                _stream.Read(buffer, 0, _useIntFileSize ? 4 : 8);
                long fileSize = _useIntFileSize ? Unsafe.As<byte, int>(ref buffer[0]) : Unsafe.As<byte, long>(ref buffer[0]);

                // 跳过
                _stream.Seek(fileSize, SeekOrigin.Current);

                // 读取属性
                var props = InternalGetFileInfoDictionary(buffer);
                var fileInfo = new FileInfo()
                {
                    FileName = file.FileName,
                    FileSize = fileSize
                };
                props.TryGetValue("A", out object propAttributes);
                if (propAttributes != null && propAttributes is int)
                    fileInfo.Attributes = (int)propAttributes;
                props.TryGetValue("L", out object propLastModifiedTimeUtc);
                if (propLastModifiedTimeUtc != null && propLastModifiedTimeUtc is DateTime)
                    fileInfo.LastModifiedTimeUtc = (DateTime)propLastModifiedTimeUtc;
                return fileInfo;
            }
            finally
            {
                s_arrayPool.Return(buffer);
            }
        }
        public async Task<FileInfo> GetFileInfoAsync(FileIndexNode file)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (!file.SkipParentValidation && !ReferenceEquals(file.Parent, this))
            {
                throw new InvalidOperationException("Parent object mismatch!");
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            _stream.Seek(file.FileOffset, SeekOrigin.Begin);

            byte[] buffer = s_arrayPool.Rent(256);
            try
            {
                // 读取节点头部
                await _stream.ReadAsync(buffer, 0, _useIntFileSize ? 4 : 8).ConfigureAwait(false);
                long fileSize = _useIntFileSize ? Unsafe.As<byte, int>(ref buffer[0]) : Unsafe.As<byte, long>(ref buffer[0]);

                // 跳过
                _stream.Seek(fileSize, SeekOrigin.Current);

                // 读取属性
                var props = await InternalGetFileInfoDictionaryAsync(buffer).ConfigureAwait(false);
                var fileInfo = new FileInfo()
                {
                    FileName = file.FileName,
                    FileSize = fileSize
                };
                props.TryGetValue("A", out object propAttributes);
                if (propAttributes != null && propAttributes is int)
                    fileInfo.Attributes = (int)propAttributes;
                props.TryGetValue("L", out object propLastModifiedTimeUtc);
                if (propLastModifiedTimeUtc != null && propLastModifiedTimeUtc is DateTime)
                    fileInfo.LastModifiedTimeUtc = (DateTime)propLastModifiedTimeUtc;
                return fileInfo;
            }
            finally
            {
                s_arrayPool.Return(buffer);
            }
        }
        internal Dictionary<string, object> InternalGetFileInfoDictionary(byte[] buffer)
        {
            var props = new Dictionary<string, object>();
            int keyLen = _stream.ReadByte();
            while (keyLen > 0)
            {
                _stream.Read(buffer, 0, keyLen + 2);
                string key = s_encoding.GetString(buffer, 0, keyLen);
                short valueLen = Unsafe.As<byte, short>(ref buffer[keyLen]);
                switch (key)
                {
                    case "A":
                        if (valueLen != 4)
                            throw new InvalidDataException();
                        _stream.Read(buffer, 0, 4);
                        props.Add("A", Unsafe.As<byte, int>(ref buffer[0]));
                        break;
                    case "L":
                        if (valueLen != 8)
                            throw new InvalidDataException();
                        _stream.Read(buffer, 0, 8);
                        props.Add("L", new DateTime(Unsafe.As<byte, long>(ref buffer[0]), DateTimeKind.Utc));
                        break;
                    default:
                        if (!props.ContainsKey(key))
                            props.Add(key, null);
                        if (valueLen > 0)
                        {
                            _stream.Seek(valueLen, SeekOrigin.Current);
                        }
                        break;
                }
                keyLen = _stream.ReadByte();
            }
            return props;
        }
        internal async Task<Dictionary<string, object>> InternalGetFileInfoDictionaryAsync(byte[] buffer)
        {
            var props = new Dictionary<string, object>();
            await _stream.ReadAsync(buffer, 0, 1).ConfigureAwait(false);
            int keyLen = buffer[0];
            while (keyLen > 0)
            {
                await _stream.ReadAsync(buffer, 0, keyLen + 2).ConfigureAwait(false);
                string key = s_encoding.GetString(buffer, 0, keyLen);
                short valueLen = Unsafe.As<byte, short>(ref buffer[keyLen]);
                switch (key)
                {
                    case "A":
                        if (valueLen != 4)
                            throw new InvalidDataException();
                        await _stream.ReadAsync(buffer, 0, 4).ConfigureAwait(false);
                        props.Add("A", Unsafe.As<byte, int>(ref buffer[0]));
                        break;
                    case "L":
                        if (valueLen != 8)
                            throw new InvalidDataException();
                        await _stream.ReadAsync(buffer, 0, 8).ConfigureAwait(false);
                        props.Add("L", new DateTime(Unsafe.As<byte, long>(ref buffer[0]), DateTimeKind.Utc));
                        break;
                    default:
                        if (!props.ContainsKey(key))
                            props.Add(key, null);
                        if (valueLen > 0)
                        {
                            _stream.Seek(valueLen, SeekOrigin.Current);
                        }
                        break;
                }
                await _stream.ReadAsync(buffer, 0, 1).ConfigureAwait(false);
                keyLen = buffer[0];
            }
            return props;
        }

        public void CopyFileTo(FileIndexNode file, string destinationPath)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (destinationPath == null)
            {
                throw new ArgumentNullException(nameof(destinationPath));
            }
            EnsureNotDisposed();

            using (var fs = OpenWriteStream(destinationPath, false))
            {
                CopyFileTo(file, fs);
            }
        }
        public void CopyFileTo(FileIndexNode file, Stream destination)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (destination == null)
            {
                throw new ArgumentNullException(nameof(destination));
            }
            if (!file.SkipParentValidation && !ReferenceEquals(file.Parent, this))
            {
                throw new InvalidOperationException("Parent object mismatch!");
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            _stream.Seek(file.FileOffset, SeekOrigin.Begin);

            byte[] buffer = s_arrayPool.Rent(4096);
            Unsafe.As<byte, long>(ref buffer[0]) = 0;
            long fileSize;
            try
            {
                _stream.Read(buffer, 0, _useIntFileSize ? sizeof(int) : sizeof(long));
                fileSize = _useIntFileSize ? Unsafe.As<byte, int>(ref buffer[0]) : Unsafe.As<byte, long>(ref buffer[0]);
                while (fileSize >= 4096)
                {
                    int count = _stream.Read(buffer, 0, 4096);
                    if (count != 4096)
                        throw new InvalidDataException();
                    destination.Write(buffer, 0, 4096);
                    fileSize -= 4096;
                }
                if (fileSize > 0)
                {
                    int count = _stream.Read(buffer, 0, (int)fileSize);
                    if (count != fileSize)
                        throw new InvalidDataException();
                    destination.Write(buffer, 0, count);
                }
            }
            finally
            {
                s_arrayPool.Return(buffer);
            }
        }
        public async Task<long> CopyFileToAsync(FileIndexNode file, string destinationPath)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (destinationPath == null)
            {
                throw new ArgumentNullException(nameof(destinationPath));
            }
            EnsureNotDisposed();

            using (var fs = OpenWriteStream(destinationPath, true))
            {
                return await CopyFileToAsync(file, fs).ConfigureAwait(false);
            }
        }
        public async Task<long> CopyFileToAsync(FileIndexNode file, Stream destination)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (destination == null)
            {
                throw new ArgumentNullException(nameof(destination));
            }
            if (!file.SkipParentValidation && !ReferenceEquals(file.Parent, this))
            {
                throw new InvalidOperationException("Parent object mismatch!");
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            _stream.Seek(file.FileOffset, SeekOrigin.Begin);

            byte[] buffer = s_arrayPool.Rent(sizeof(long));
            Unsafe.As<byte, long>(ref buffer[0]) = 0;
            long fileSize;
            try
            {
                await _stream.ReadAsync(buffer, 0, _useIntFileSize ? sizeof(int) : sizeof(long)).ConfigureAwait(false);
                fileSize = _useIntFileSize ? Unsafe.As<byte, int>(ref buffer[0]) : Unsafe.As<byte, long>(ref buffer[0]);
            }
            finally
            {
                s_arrayPool.Return(buffer);
            }

            return await StreamToStreamCopy.CopyAsync(_stream, destination, fileSize).ConfigureAwait(false);
        }

        public Stream OpenFileStream(FileIndexNode file)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (!file.SkipParentValidation && !ReferenceEquals(file.Parent, this))
            {
                throw new InvalidOperationException("Parent object mismatch!");
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            var stream = OpenReadStream(_path, false);
            stream.Seek(file.FileOffset, SeekOrigin.Begin);

            // OPTIMIZATION 使用stackalloc
            byte[] buffer = s_arrayPool.Rent(sizeof(long));
            Unsafe.As<byte, long>(ref buffer[0]) = 0;
            long fileSize;
            try
            {
                stream.Read(buffer, 0, _useIntFileSize ? sizeof(int) : sizeof(long));
                fileSize = _useIntFileSize ? Unsafe.As<byte, int>(ref buffer[0]) : Unsafe.As<byte, long>(ref buffer[0]);
            }
            finally
            {
                s_arrayPool.Return(buffer);
            }

            return new TruncatedStream(stream, fileSize, false);
        }

        public async Task<Stream> OpenFileStreamAsync(FileIndexNode file)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (!file.SkipParentValidation && !ReferenceEquals(file.Parent, this))
            {
                throw new InvalidOperationException("Parent object mismatch!");
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            var stream = OpenReadStream(_path, true);
            stream.Seek(file.FileOffset, SeekOrigin.Begin);

            byte[] buffer = s_arrayPool.Rent(sizeof(long));
            long fileSize;
            try
            {
                await stream.ReadAsync(buffer, 0, _useIntFileSize ? sizeof(int) : sizeof(long)).ConfigureAwait(false);
                fileSize = _useIntFileSize ? Unsafe.As<byte, int>(ref buffer[0]) : Unsafe.As<byte, long>(ref buffer[0]);
            }
            finally
            {
                s_arrayPool.Return(buffer);
            }

            return new TruncatedStream(stream, fileSize, false);
        }


        public Stream SwitchToFileStream(FileIndexNode file, bool disposeParent = true)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (!file.SkipParentValidation && !ReferenceEquals(file.Parent, this))
            {
                throw new InvalidOperationException("Parent object mismatch!");
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            _stream.Seek(file.FileOffset, SeekOrigin.Begin);

            // OPTIMIZATION 使用stackalloc
            byte[] buffer = s_arrayPool.Rent(sizeof(long));
            Unsafe.As<byte, long>(ref buffer[0]) = 0;
            long fileSize;
            try
            {
                _stream.Read(buffer, 0, _useIntFileSize ? sizeof(int) : sizeof(long));
                fileSize = _useIntFileSize ? Unsafe.As<byte, int>(ref buffer[0]) : Unsafe.As<byte, long>(ref buffer[0]);
            }
            finally
            {
                s_arrayPool.Return(buffer);
            }

            Stream s;
            if (disposeParent)
            {
                s = new TruncatedStream(_stream, fileSize, false);
                _stream = null;
                this.Dispose();
            }
            else
            {
                s = new TruncatedStream(_stream, fileSize, true);
            }
            return s;
        }

        public async Task<Stream> SwitchToFileStreamAsync(FileIndexNode file, bool disposeParent = true)
        {
            if (file == null)
            {
                throw new ArgumentNullException(nameof(file));
            }
            if (!file.SkipParentValidation && !ReferenceEquals(file.Parent, this))
            {
                throw new InvalidOperationException("Parent object mismatch!");
            }
            if (!BitConverter.IsLittleEndian)
            {
                throw new PlatformNotSupportedException();
            }
            EnsureNotDisposed();

            _stream.Seek(file.FileOffset, SeekOrigin.Begin);

            byte[] buffer = s_arrayPool.Rent(sizeof(long));
            Unsafe.As<byte, long>(ref buffer[0]) = 0;
            long fileSize;
            try
            {
                await _stream.ReadAsync(buffer, 0, _useIntFileSize ? sizeof(int) : sizeof(long)).ConfigureAwait(false);
                fileSize = _useIntFileSize ? Unsafe.As<byte, int>(ref buffer[0]) : Unsafe.As<byte, long>(ref buffer[0]);
            }
            finally
            {
                s_arrayPool.Return(buffer);
            }

            Stream s;
            if (disposeParent)
            {
                s = new TruncatedStream(_stream, fileSize, false);
                _stream = null;
                this.Dispose();
            }
            else
            {
                s = new TruncatedStream(_stream, fileSize, true);
            }
            return s;
        }


        public class FileIndexNode
        {
            internal bool SkipParentValidation { get; set; }
            internal IndexedFilePackage Parent { get; set; }
            public string FileName { get; internal set; }
            internal long FileOffset { get; set; }

            internal FileIndexNode(IndexedFilePackage parent)
            {
                Parent = parent;
                SkipParentValidation = false;
            }

            [EditorBrowsable(EditorBrowsableState.Never)]
            public FileIndexNode DangerousSkipParentValidation()
            {
                return new FileIndexNode(null)
                {
                    SkipParentValidation = true,
                    FileName = FileName,
                    FileOffset = FileOffset
                };
            }
        }

        public class FileInfo
        {
            public long FileSize { get; set; }
            public string FileName { get; set; }
            public int? Attributes { get; set; }
            public DateTime? LastModifiedTimeUtc { get; set; }
        }

        #region IDisposable Support
        private bool disposedValue = false; // 要检测冗余调用

        private void EnsureNotDisposed()
        {
            if (disposedValue)
            {
                throw new ObjectDisposedException(nameof(IndexedFilePackage));
            }
        }

        protected virtual void Dispose(bool disposing)
        {
            if (!disposedValue)
            {
                if (disposing)
                {
                    // 释放托管状态(托管对象)。
                    _stream?.Dispose();
                }

                // 释放未托管的资源(未托管的对象)并在以下内容中替代终结器。
                // 将大型字段设置为 null。
                _stream = null;

                disposedValue = true;
            }
        }

        // 仅当以上 Dispose(bool disposing) 拥有用于释放未托管资源的代码时才替代终结器。
        ~IndexedFilePackage()
        {
            // 请勿更改此代码。将清理代码放入以上 Dispose(bool disposing) 中。
            Dispose(false);
        }

        // 添加此代码以正确实现可处置模式。
        public void Dispose()
        {
            // 请勿更改此代码。将清理代码放入以上 Dispose(bool disposing) 中。
            Dispose(true);
            // 如果在以上内容中替代了终结器，则取消注释以下行。
            GC.SuppressFinalize(this);
        }
        #endregion

    }
}
